package code.oldCode.classic150;

import utils.ListNode;
import utils.TreeNode;

/**
 * @author cuihaoran
 * @date 2025/2/20
 */
public class Classic150_divideAndConquer {

    /* 108. 将有序数组转换为二叉搜索树 */
    public TreeNode sortedArrayToBST(int[] nums) {
        int len = nums.length;
        TreeNode root = new TreeNode();
        sortedArrayToBST_divide(nums, 0, len - 1, root);
        return root;
    }

    public void sortedArrayToBST_divide(int[] nums, int begin, int end, TreeNode root) {
        int half = (begin + end) / 2;
        root.val = nums[half];

        if (begin <= half - 1) {
            root.left = new TreeNode();
            sortedArrayToBST_divide(nums, begin, half - 1, root.left);
        }
        if (half + 1 <= end) {
            root.right = new TreeNode();
            sortedArrayToBST_divide(nums, half + 1, end, root.right);
        }
    }

    /* 148. 排序链表 */
    public ListNode sortList(ListNode head) {
        return null;
    }

    public static void main(String[] args) {
        Classic150_divideAndConquer c = new Classic150_divideAndConquer();
        int[] test = new int[]{-10, -3, 0, 5, 9};
        System.out.println(c.sortedArrayToBST(test));
    }
}
